public class Solution445 {

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        StringBuilder s1=new StringBuilder();
        while (l1!=null){
            s1.append(l1.val);
            l1=l1.next;
        }
        StringBuilder s2=new StringBuilder();
        while (l2!=null){
            s2.append(l2.val);
            l2=l2.next;
        }
        String sum=add(s1.toString(),s2.toString());
        ListNode first=new ListNode(-1,null);
        ListNode cur=first;
        for (int i=0;i<sum.length();i++){
            ListNode l=new ListNode(sum.charAt(i)-'0',null);
            cur.next=l;
            cur=cur.next;
        }
        return first.next;
    }

    String add(String a,String b){
        int max = Math.max(a.length(), b.length())+1;
        int[] fa=new int[max];
        int[] fb=new int[max];
        int[] fc=new int[max];
        for (int i=0;i<a.length();i++){
            fa[a.length()-i-1]=a.charAt(i)-'0';
        }
        for (int i=0;i<b.length();i++){
            fb[b.length()-i-1]=b.charAt(i)-'0';
        }
        int c=0;
        for (int i=0;i<max;i++){
            fc[i]=fa[i]+fb[i]+c;
            c=0;
            if (fc[i]>=10){
                c=1;
                fc[i]-=10;
            }
        }
        int start=max-1;
        if (fc[max-1]==0){
            start--;
        }
        StringBuilder stringBuilder=new StringBuilder();
        for (int i=start;i>=0;i--){
            stringBuilder.append(fc[i]);
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution445().addTwoNumbers(new ListNode(7,new ListNode(2,new ListNode(4,new ListNode(3)))),new ListNode(5,new ListNode(6,new ListNode(4)))).next.next.val);
    }
}
